package com.zk.algorithm.dynamicprogramming;

/**
 *
 * 最长公共子串
 *
 * Input : X = "abcdxyz", y = "xyzabcd"
 Output : 4
 The longest common substring is "abcd" and is of
 length 4.


 https://www.geeksforgeeks.org/longest-common-substring-dp-29/
 *
 * @author zk
 */
public class LongestCommonSubstring {

    /**
     * 解法一：动态规划
     *
     * @param X
     * @param i
     * @param Y
     * @param j
     * @param count
     * @return
     */
    public int lcs(String X, int i, String Y, int j, int count) {
        if (i == 0 || j == 0) {
            return count;
        }

        if (X.charAt(i - 1) == Y.charAt(j - 1)) {
            count = lcs(X, i - 1, Y, j - 1, count + 1);
        }

        count = Math.max(
                count,
                Math.max(lcs(X, i, Y, j - 1, 0), lcs(X, i - 1, Y, j, 0))
        );

        return count;
    }

    /**
     * 解法二：后缀数组和高度数组
     *
     * abcdbcefa 0
     * bcdbcefa 1
     * cdbcefa 2
     * dbcefa 3
     * bcefa 4
     * cefa 5
     * efa 6
     * fa 7
     * a 8
     *
     * a 8
     * abcdbcefa 0
     * bcdbcefa 1
     * bcefa 4
     * cdbcefa 2
     * cefa 5
     * dbcefa 3
     * efa 6
     * fa 7
     *
     * @return
     */
    public int lcs2() {
        return -1;
    }

    public static void main(String[] args) {
        String X = "abcdxyz";
        String Y = "xyzabcd";

        X = "ABRACADABRA";
        Y = "ECADADABRBCRDAR";

        LongestCommonSubstring longestCommonSubstring = new LongestCommonSubstring();
        System.out.println(longestCommonSubstring.lcs(X, X.length(), Y, Y.length(), 0));

        System.out.println(longestCommonSubstring.lcs2());
    }

}
